// Tags:
#include <cctype>
#include <cstdio>

typedef long long ll;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int mod = 998244353, N = 2e7 + 5;
int T, n;
ll f[N], fac[N], inv[N], finv[N];

inline ll qpow(ll base, int exp) {
  ll res = 1;
  while (exp) {
    if (exp & 1) res = res * base % mod;
    base = base * base % mod;
    exp >>= 1;
  }
  return res;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("power.in", "r", stdin);
  freopen("power.out", "w", stdout);
#endif
#endif

  read(T);
  f[1] = 1, f[2] = 2, f[3] = 6;
  finv[0] = inv[0] = fac[0] = 1;
  for (int i = 1; i < N; ++i) fac[i] = fac[i - 1] * i % mod;
  finv[N - 1] = qpow(fac[N - 1], mod - 2);
  for (int i = N - 2; i >= 1; --i) finv[i] = finv[i + 1] * (i + 1) % mod;
  for (int i = 1; i < N; ++i) inv[i] = finv[i] * fac[i - 1] % mod;
  for (int i = 4; i < N - 1; ++i) {
    f[i] = (((3ll * i * f[i - 1] % mod + (ll)(i + 3) * f[i - 2] % mod) -
             ((3ll * i - 6) * f[i - 3] % mod)) +
            mod) %
           mod;
    f[i] = f[i] * inv[i + 1] % mod;
  }
  while (T--) { printf("%lld\n", f[read(n)]); }
  return 0;
}